package Tu;

/**
 * Created by Administrator on 2017/11/24/024.
 */
public class ShortestPath {
    // 求取最短路径
    public static String[][] getShortestPath(int data[][]) {

        int length = data.length;
        String path[][] = new String[length][length];
        for (int i = 0; i < data.length; i++)
            for (int j = 0; j < data[i].length; j++) {
                if (data[i][j] > 0)
                    path[i][j] = (i + 1) + "-->" + (j + 1);
                else
                    path[i][j] = "不通";
            }
        int k = 0;
        while (k < length) {// 循环将各行加入,即计算将k作为最大通过节点之后的最短路径
            for (int i = 0; i < length; i++) {
                if (data[k][i] > 0) {// 如果这个节点连通了其他节点,则察看是否将影响到当前的最短路径
                    for (int m = 0; m < length; m++) {
                        int temp[] = data[m];
                        if (temp[k] > 0) {// 如果加入当前节点和加入的节点之间是相通的,执行下面的
                            if (temp[i] < 0) {
                                if (i != m) {
                                    temp[i] = temp[k] + data[k][i];
                                    path[m][i] = (m + 1) + "-->" + (k + 1)
                                            + "-->" + (i + 1);
                                }
                            } else {
                                temp[i] = Math.min(temp[k] + data[k][i],
                                        temp[i]);
                                path[m][i] = path[m][k] + "-->"
                                        + (i + 1);
                            }
                        }
                        data[m] = temp;
                    }
                }
            }
            k++;
        }
        return path;
    }

    public static void main(String[] args) {
        int data[][] = { { -1, 1, 2, -1, -1, -1 }, { -1, -1, 1, 3, -1, 7 },
                { -1, -1, -1, 1, 2, -1 }, { -1, -1, -1, -1, -1, 3 },
                { -1, -1, -1, -1, -1, 6 }, { -1, -1, -1, -1, -1, -1 } };
        String pathShow[][] = getShortestPath(data);
        for (int i = 0; i < data.length; i++) {
            for (int j = 0; j < data[i].length; j++) {
                if (data[i][j] > 0) {
                    System.out.print("节点" + (i + 1) + "到节点" + (j + 1)
                            + "的最短路径是:" + data[i][j]);
                    System.out.println("    路径是" + pathShow[i][j]);
                }
            }
        }
        System.out.println("其余没列出的节点之间是不通的");
    }
}
